package com.datastructures.sort;

/**
 * 希尔排序
 * @author MaoLin Wang
 * @date 2019/10/2817:43
 */
public class ShellSort {
    public static void main(String[] args) {

      //  int[] arr={214,32,11,2,3,21,66,4};

        //shellSort2(arr);
        int[] arr =new int[3000000];
        for (int i=0;i<3000000;i++){
            arr[i]=(int)(Math.random()*3000000);
        }
        System.out.println("2");
        long begintime=System.currentTimeMillis();
        shellSort2(arr);

        long endtime=System.currentTimeMillis();
        System.out.println("用时："+(endtime-begintime)+"ms");
    }
    public static void shellSort(int[]arr){
        int temp=0;
        int count=0;
        for (int group =arr.length/2;group>0;group/=2){
            for (int i=group;i<arr.length;i++){
                for (int j=i-group;j>=0;j-=group){
                    if (arr[j]>arr[j+group]){
                        temp=arr[j];
                        arr[j]=arr[j+group];
                        arr[j+group]=temp;
                    }
                }
            }
          //  System.out.println("第"+(++count)+"次排序结果：");
           // System.out.println(Arrays.toString(arr));
        }
    }

    public static void shellSort2(int arr[]) {

        for (int group = arr.length / 2; group > 0; group /= 2) {
            for (int i = group; i < arr.length; i++) {
                int j = i;
                int temp = arr[j];
                if (arr[j] < arr[j - group]) {
                    while ((j - group) >= 0 && temp < arr[j - group]) {
                        /**
                         *  开始移动，将比arr[j]大的arr[j-group]、arr[j-group-group]......按顺序移动到后一个增量的位置
                         *   如 3, 2, 11, 21, 66, 32, 214, 4
                         *   在group减少到2，比较32和4的时候
                         *  1. 4<32  且满足while条件， 所以将32移动到4,temp=4，j=5，指向32的位置
                         *   此时的数据为:3, 2, 11, 21, 66, 32, 214, 32
                         *  2.继续while循环
                         *      j-group=3>0   temp=4<arr[3]=21，满足while条件
                         *      执行arr[j]=arr[j-group] -> 将21的位置移动到32,temp仍然为一开始的4,j=3，指向21的位置
                         *    此时数据为：3, 2, 11, 21, 66, 21, 214, 32
                         *  3.继续循环while
                         *      j-group=1>0  temp=4>arr[1]=2 不满足while条件，退出循环
                         *  4.此时j=3，将temp=4赋值给arr[j]
                         *     此时数据为：3, 2, 11, 4, 66, 21, 214, 32
                         */

                        arr[j] = arr[j - group];
                        j -= group;
                    }
                    //结束while循环后，将temp插入到arr[j]
                    arr[j] = temp;
                }
            }
            //  System.out.println("第"+(++count)+"次排序结果：");
            // System.out.println(Arrays.toString(arr));
        }
    }
}
